← All Articles

[BAEKJOON] 17940. 지하철

Posted on

문제 :

대학원생인 형욱이는 연구실에 출근할 때 주로 지하철을 이용한다. 지하철은 A와 B, 두 개의 회사에서 운영하고 있다. 두 회사는 경쟁사 관계로 사람들이 상대 회사의 지하철을 이용하는 것을 매우 싫어한다. 그래서 A와 B는 모두 상대 회사의 지하철로 환승할 때 마다 비싼 요금을 받고 있다.

형욱이는 가난한 대학원생이기 때문에 돈을 아끼는 것이 가장 중요하다. 형욱이에게 최적의 출근경로를 찾아주자. 최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다. 여기에서의 환승은 이동하면서 지하철역을 운영하는 회사가 바뀔 때 마다 환승 1회로 계산한다.

image

위의 그림에서 원은 지하철역을 의미하고 선들은 지하철역들이 연결되어 있는 지를 나타낸다. 흰색으로 표시된 지하철역은 A회사가 운영하는 지하철역이고 검은색으로 표시된 역은 B회사가 운영하는 지하철역이다. 이 때 붉게 표시된 경로로 이동하는 것이 환승 2회로 가장 적게 환승하면서 시간이 가장 짧은 경로이다.


입력 :

첫째 줄에 지하철역의 수 N과 도착지의 번호 M이 공백을 사이에 두고 정수로 주어진다. 지하철역은 순서대로 0 부터 N-1까지 존재하며 출발지는 항상 0 이다. (2 ≤ N ≤ 1000, 0 < M < 1000)

그 다음 N 줄에 걸쳐 각각의 지하철역을 운영하는 회사의 정보 Ci(0 ≤ i < N)가 0 또는 1로 주어진다. 0은 A회사를 뜻하고 1은 B회사를 뜻한다.

그 다음 N 줄은 지하철역간의 연결 상태 Eij(0 ≤ Eij ≤ 1000)가 정수로 주어진다. Eij가 0인 경우 i번째 역과 j번째 역이 연결되어 있지 않음을 의미하고 0보다 클 경우 두 역이 연결되어 있으며 이동시간이 Eij라는 것을 의미한다.


출력 :

최적의 경로를 이용할 때 환승 횟수와 총 소요 시간을 공백으로 구분하여 출력한다.

또한 출발지와 도착지는 무조건 연결되어 있음이 보장된다.



풀이 :

문제는 다익스트라 알고리즘을 어느정도 능숙히 이해했다면 두 가지 조건을 활용하여 환승횟수가 가장 적으면서 소요시간도 짧은 최단 경로를 구하는 문제라는 것을 쉽게 알아챌 수 있다.

기존의 다익스트라 알고리즘의 경우 간선의 가중치의 합 단일 조건 만으로 최단 경로를 구해줬다면, 본 문제는 우선순위 큐를 구현할 때 첫번째 조건으로 환승횟수가 적은 순으로 꺼내주고 만약 환승횟수가 같다면 두번째 조건으로 소요시간이 짧은 순으로 최단경로를 계산해주면 쉽게 문제를 해결할 수 있다.

다익스트라 알고리즘 구현자체가 능숙하지 않다면 두가지 조건을 활용해주어야 하기 때문에 조금은 복잡해질 수 있는 문제인 것 같다.



코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>

#define pii pair<int, int>
#define MAX 987654321

using namespace std;
typedef struct Qnode {
    int idx;
    int transfer;
    int dist;
} Qnode;

struct compare {
    bool operator()(Qnode a, Qnode b) {
        if (a.transfer == b.transfer) return a.dist > b.dist;
        return a.transfer > b.transfer;
    }
};

vector<vector<pii>> adj;
int *company, n, dest;

void dijkstra() {
    priority_queue<Qnode, vector<Qnode>, compare> pq;
    bool *visit = new bool[n]{false};

    pq.push(Qnode{0, 0, 0});
    while (!pq.empty()) {
        int curidx = pq.top().idx, curt = pq.top().transfer, curd = pq.top().dist, size = adj[curidx].size();
        pq.pop();
        if (visit[curidx]) continue;
        visit[curidx] = true;
        if (curidx == dest) {
            cout << curt << ' ' << curd << '\n';
            return;
        }

        for (int k = 0; k < size; k++) {
            int cmpidx = adj[curidx][k].first, cmpdist = adj[curidx][k].second;
            if (company[curidx] == company[cmpidx]) pq.push(Qnode{cmpidx, curt, curd + cmpdist});
            else pq.push(Qnode{cmpidx, curt + 1, curd + cmpdist});
        }
    }
}

int main() {
    int i, j, num;
    cin >> n >> dest;
    company = new int[n];
    adj.resize(n);

    for (i = 0; i < n; i++)
        cin >> company[i];
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            cin >> num;
            if (num) adj[i].emplace_back(j, num);
        }
    dijkstra();
    return 0;
}

AlgorithmalgorithmbaekjoonC++